package com.kailing.bootBatch.A.listnode;

import java.util.List;

/**
 * <h3>partitionjob</h3>
 * <p>单链表操作</p>
 *
 * @author : hduong
 * @version : 1.0
 * @date : 2019-12-19 14:21
 **/
public class Solution {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    /**
     * 功能描述: 
     * <链表的赋值操作： 其实可以理解成 指针的移位操作>
     *     代表的是： 左边的指针移动到右边的位置
     *     上面的不准确
     *     准确的是： .next标识位置 ; 其他的标识指针
     * @param head
     * @date : 2019/12/19 14:28
     * @return : com.kailing.bootBatch.A.listnode.Solution.ListNode
     * @author : hduong
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        //pre代表是新链表: 指向原链表摘下来的表头
        ListNode pre = null;
        ListNode next;
        while (head != null) {
            //1: 保存原链表
            //2：将原链表头取下来， 添加到新链表
            //3：pre 右移动
            //4：head 右边移动
            next = head.next;
            //将head的下一个指向null
            head.next = pre;
            //将pre移动到新的链表头
            pre = head;
            //再将head移动到旧链表的头 next
            head = next;
        }
        return pre;
    }

    public static ListNode reverseListRecusion(ListNode head) {
        ListNode newHead;
        if(head == null || head.next == null) {
            return head;
        }
        //head.next作为剩余部分的头指针
        //5 在 4的基础上：
        //newHead = 5 : head = 3 --> head.next=4 ;
        // head = 4; head.next = 5;
        // head =4 ; newHead = 5;
        // head = 3 ; newHead =
        newHead = reverseListRecusion(head.next);
        //4 -> 5 -> null :
        // head = 4;
        //4.5.null -> 移动到了head 5.next 移动到了head
        // head 指向了 head。next。next 指向了最后一个
        head.next.next = head;
        head.next = null;
        return newHead;

    }

    public static void main(String[] args) {
        ListNode root = new ListNode(1);
        ListNode root2 = new ListNode(2);
        ListNode root3 = new ListNode(3);
        ListNode root4 = new ListNode(4);
        ListNode root5 = new ListNode(5);

        root.next = root2;
        root2.next = root3;
        root3.next = root4;
        root4.next = root5;

        reverseListRecusion(root);
    }
}
